import java.util.ArrayList;

public class FeatureExtraction
{
	// Crossing (vertical, horizontal)
	public static int[][] crossing(int[][] pattern, String patternName, boolean debugging)
	{
		int height = pattern.length;
		int width = pattern[0].length;
		
		int crossingCount = 0;
		
		// Results
		int[][] results = new int[2][];
		results[0] = new int[height];
		results[1] = new int[width];
		
		// Horizontal crossing
		for (int i = 0; i != results[0].length; ++i)
		{
			for (int j = 0; j != width - 1; ++j)
			{
				if (pattern[i][j] == 1 && pattern[i][j + 1] == 0)
				{
					++crossingCount;
				}
			}
				
			results[0][i] = crossingCount;
			crossingCount = 0;
		}
		
		// Vertical crossing
		for (int i = 0; i != results[1].length; ++i)
		{
			for (int j = 0; j != height - 1; ++j)
			{
				if (pattern[j][i] == 1 && pattern[j + 1][i] == 0)
				{
					++crossingCount;
				}
			}
			
			results[1][i] = crossingCount;
			crossingCount = 0;
		}
		
		if (debugging)
		{
			System.out.print("The pattern " + patternName + " has the following crossing results. ");
			System.out.println("Horizontal crossings: ");
			
			for (int i = 0; i != results[0].length; ++i)
			{
				System.out.println("Row " + (i + 1) + ": " + results[0][i] + (results[0][i] == 1 ? " crossing." : " crossings."));
			}
			
			System.out.println("\nVertial crossings: ");
			
			for (int i = 0; i != results[1].length; ++i)
			{
				System.out.println("Column " + (i + 1) + ": " + results[1][i] + (results[1][i] == 1 ? " crossing." : " crossings."));
			}
			
			System.out.println();
		}
		
		return results;
	}
	
	// Distances
	public static int[][] distances(int[][] pattern, String patternName, boolean debugging)
	{
		int height = pattern.length;
		int width = pattern[0].length;
		
		int distance = 0;
		boolean found = false;
		
		// Results
		int[][] results = new int[2][];
		results[0] = new int[height];
		results[1] = new int[width];
		
		// Horizontal distance
		for (int i = 0; i != results[0].length; ++i)
		{
			for (int j = 0; j != width; ++j)
			{
				if (pattern[i][j] == 1)
				{
					distance = j;
					found = true;
					break;
				}
			}
			
			if (!found)
			{
				distance = -1;
			}
			
			results[0][i] = distance;
			distance = 0;
			found = false;
		}
		
		// Vertical crossing
		for (int i = 0; i != results[1].length; ++i)
		{
			for (int j = 0; j != height; ++j)
			{
				if (pattern[j][i] == 1)
				{
					distance = j;
					found = true;
					break;
				}
			}
			
			if (!found)
			{
				distance = -1;
			}
			
			results[1][i] = distance;
			distance = 0;
			found = false;
		}
		
		if (debugging)
		{
			System.out.print("The pattern " + patternName + " has the following distance results. ");
			System.out.println("Horizontal distances: ");
			
			for (int i = 0; i != results[0].length; ++i)
			{
				if (results[0][i] != -1)
					System.out.println("Row " + (i + 1) + ": Distance of " + results[0][i]);
				else
					System.out.println("Row " + (i + 1) + ": No pixel in this row.");
			}
			
			System.out.println("\nVertial distances: ");
			
			for (int i = 0; i != results[1].length; ++i)
			{
				if (results[1][i] != -1)
					System.out.println("Column " + (i + 1) + ": Distance of " + results[1][i]);
				else
					System.out.println("Column " + (i + 1) + ": No pixel in this column.");
			}
			
			System.out.println();
		}
		
		return results;
	}
	
	// Profiles (Vertical, horizontal)
	public static int[][] profiles(int[][] pattern, String patternName, boolean debugging, boolean graphical)
	{
		int height = pattern.length;
		int width = pattern[0].length;
		
		int pixelCount = 0;
		
		// Results
		int[][] results = new int[2][];
		results[0] = new int[height];
		results[1] = new int[width];
		
		// Horizontal profile
		for (int i = 0; i != results[0].length; ++i)
		{
			for (int j = 0; j != width; ++j)
			{
				if (pattern[i][j] == 1)
				{
					++pixelCount;
				}
			}
			
			results[0][i] = pixelCount;
			pixelCount = 0;
		}
		
		// Vertical crossing
		for (int i = 0; i != results[1].length; ++i)
		{
			for (int j = 0; j != height; ++j)
			{
				if (pattern[j][i] == 1)
				{
					++pixelCount;
				}
			}
			
			results[1][i] = pixelCount;
			pixelCount = 0;
		}
		
		if (debugging)
		{
			System.out.print("The pattern " + patternName + " has the following profile results. ");
			System.out.println("Horizontal profile: ");
			
			if (graphical)
			{
				for (int i = 0; i != results[0].length; ++i)
				{
					for (int count = 0; count != results[0][i]; ++count)
					{
						System.out.print("@");
					}
					
					if (results[0][i] == 0)
					{
						System.out.print("-");
					}
						
					System.out.println();
				}
			
				System.out.println("\nVertial profile: ");
			
				for (int i = 0; i != results[1].length; ++i)
				{
					for (int count = 0; count != results[1][i]; ++count)
					{
						System.out.print("@");
					}
					
					if (results[1][i] == 0)
					{
						System.out.print("-");
					}
						
					System.out.println();
				}
			}			
			else
			{
				for (int i = 0; i != results[0].length; ++i)
				{
					System.out.println("Row " + (i + 1) + ": " + results[0][i] + (results[0][i] == 1 ? " pixel." : " pixels."));
				}
			
				System.out.println("\nVertial profile: ");
			
				for (int i = 0; i != results[1].length; ++i)
				{
					System.out.println("Column " + (i + 1) + ": " + results[1][i] + (results[1][i] == 1 ? " pixel." : " pixels."));
				}
			}
			
			System.out.println();
		}
		
		return results;
	}
	
	// Chain Code
	public static ArrayList<Integer> chainCode(int[][] pattern, String patternName, boolean debugging)
	{	
		boolean done = false;
		
		int height = pattern.length;
		int width = pattern[0].length;
		
		int x = 0, y = 0, newX = 0, newY = 0, code = 0, startingCode = 0;
		
		boolean[][] visited = new boolean[height][width];
		int[] neighbours = new int[8];
		
		ArrayList<Integer> toVisitX = new ArrayList<Integer>();
		ArrayList<Integer> toVisitY = new ArrayList<Integer>();
		ArrayList<Integer> toVisitCode = new ArrayList<Integer>();
		ArrayList<Integer> chainCode = new ArrayList<Integer>();
		
		int numNeighbours = 0;
		
		// Find an end point to start at
		ArrayList<Integer> endPoint = findEndPoints(pattern, patternName, false, false);
		x = endPoint.get(0);
		y = endPoint.get(1);
		
		// Determine the entire chain code
		do
		{
			// Determine a chain code segment from a starting point until there's nothing else to visit
			do
			{
				// We have visited the starting point
				visited[y][x] = true;
				
				// Store this point's neighbours that have not yet been visited
					// Direct neighbours
					if (!visited[y - 1][x]) neighbours[0] = pattern[y - 1][x];
					if (!visited[y][x + 1]) neighbours[1] = pattern[y][x + 1];
					if (!visited[y + 1][x]) neighbours[2] = pattern[y + 1][x];
					if (!visited[y][x - 1]) neighbours[3] = pattern[y][x - 1];
					
					// Diagonal neighbours
					if (!visited[y - 1][x + 1]) neighbours[4] = pattern[y - 1][x + 1];
					if (!visited[y + 1][x + 1]) neighbours[5] = pattern[y + 1][x + 1];
					if (!visited[y + 1][x - 1]) neighbours[6] = pattern[y + 1][x - 1];
					if (!visited[y - 1][x - 1]) neighbours[7] = pattern[y - 1][x - 1];
				
				// Examine each neighbour's value to determine the next point to visit
				// starting with the more important direct neighbours
				for (int i = 0; i != neighbours.length; ++i)
				{
					// If the neighbour can be visited...
					if (neighbours[i] == 1)
					{
						// Count it
						++numNeighbours;
						
						// If this is the first valid neighbour, then we will move to that point
						if (numNeighbours == 1)
						{
							// Find the point's chain code and store the point's coordinates
							switch (i)
							{
								// Up
								case 0:
									code = 2;
									newX = x;
									newY = y - 1;
									break;
								// Right
								case 1:
									code = 0;
									newX = x + 1;
									newY = y;
									break;
								// Down
								case 2:
									code = 6;
									newX = x;
									newY = y + 1;
									break;
								// Left	
								case 3:
									code = 4;
									newX = x - 1;
									newY = y;
									break;
								// Up-Right	
								case 4:
									code = 1;
									newX = x + 1;
									newY = y - 1;
									break;
								// Down-Right
								case 5:
									code = 7;
									newX = x + 1;
									newY = y + 1;
									break;
								// Down-Left
								case 6:
									code = 5;
									newX = x - 1;
									newY = y + 1;
									break;
								// Up-Left
								case 7:
									code = 3;
									newX = x - 1;
									newY = y - 1;
									break;
							}
						}
						
						// If not (meaning that there is a fork), this point
						// must be visited later, so we must store it						
						else
						{
							switch (i)
							{
								case 1:
									toVisitCode.add(0);
									toVisitX.add(x + 1);
									toVisitY.add(y);
									break;
									
								case 2:
									toVisitCode.add(6);
									toVisitX.add(x);
									toVisitY.add(y + 1);
									break;
									
								case 3:
									toVisitCode.add(4);
									toVisitX.add(x - 1);
									toVisitY.add(y);
									break;
									
								case 4:
									toVisitCode.add(1);
									toVisitX.add(x + 1);
									toVisitY.add(y - 1);
									break;
									
								case 5:
									toVisitCode.add(7);
									toVisitX.add(x + 1);
									toVisitY.add(y + 1);
									break;
									
								case 6:
									toVisitCode.add(5);
									toVisitX.add(x - 1);
									toVisitY.add(y + 1);
									break;
									
								case 7:
									toVisitCode.add(3);
									toVisitX.add(x - 1);
									toVisitY.add(y - 1);
									break;
							}
						}
					}
				}
				
				// If there are no new neighbours to visit, we have reached a dead end
				// and must start again from one of the points that we have missed
				if (numNeighbours == 0)
				{
					break;
				}
				
				// If we found a neighbour...
				
				// Trim the list of points to visit
				toVisitX.trimToSize();
				toVisitY.trimToSize();
				toVisitCode.trimToSize();
				
				// We move to the point we found
				// The chain code is updated and we update our current coordinates
				chainCode.add(code);
				x = newX;
				y = newY;
				
				// Reset all values that need to be reset
					for (int i = 0; i != neighbours.length; ++i)
					{
						neighbours[i] = 0;
					}
					
					numNeighbours = 0;
				
			} while (true); // Infinite loop, must be broken out of
			
			// Search for a new starting point from the list of points that we saved
			do
			{
				// If there are no more points to visit, we're done
				if (toVisitX.isEmpty())
				{
					done = true;
					break;
				}
				
				// If not, we start the procedure again at an unvisited point,
				// taking the first point in the saved list
				x = toVisitX.get(0);
				y = toVisitY.get(0);
				startingCode = toVisitCode.get(0);
				
				// We're going to visit that point, so we remove it
				toVisitX.remove(0);
				toVisitY.remove(0);
				toVisitCode.remove(0);
				
			} while(visited[y][x]); // We look for a new point to visit until we find one in the list
									// that has not yet been visited. A saved point could potentially
									// have been visited the iteration after it was saved
			
			// If we're done, we break
			if (done)
				break;
			
			// If not, add what the transition would have been had this alternate path been chosen
			chainCode.add(startingCode);
			chainCode.trimToSize();
			
		} while(true);
		
		// Trim the chain code
		chainCode.trimToSize();
		
		if (debugging)
		{
			// Print the chain code
			System.out.println("The chain code for pattern " + patternName + " is: ");
			
			for (Integer i : chainCode)
			{
				System.out.print(i + " ");
			}
			
			System.out.println();
		}
		
		return chainCode;
	}
	
	// Find endpoints of the pattern
	// Format of returned arrayList is x1, y1, x2, y2, ...
	public static ArrayList<Integer> findEndPoints(int[][] pattern, String patternName, boolean continuous, boolean debugging)
	{
		int height = pattern.length;
		int width = pattern[0].length;
		ArrayList<Integer> endPoints = new ArrayList<Integer>();
		
		int x = 0, y = 0, neighbourCount = 0, endPointCount = 0;
		boolean breakIf = false;
		
		for (int i = 1; i != height - 1; ++i)
		{
			for (int j = 1; j != width - 1; ++j)
			{
				// Skip empty pixels
				if (pattern[i][j] == 0) continue;
				
				// Checks to see the number of connected pixels
				for (int k = i - 1; k != i + 2; ++k)
				{
					for (int l = j - 1; l != j + 2; ++l)
					{
						// Skip the pixel itself
						if (l == j && k == i) continue;
						
						// Increment neighbour count
						if (pattern[k][l] == 1) ++neighbourCount;
						
						// Break if the pixel has two or more neighbours
						if (neighbourCount >= 2)
						{
							breakIf = true;
							break;
						}
					}
					
					if (breakIf)
					{
						breakIf = false;
						break;
					}
				}
				
				if (neighbourCount < 2)
				{
					++endPointCount;
					
					// Indexes are modified to be more intuitive
					x = j;
					y = i;
					
					if (debugging) System.out.println("The pattern " + patternName + " has endpoint " + x + ", " + y + ".");
					
					endPoints.add(x);
					endPoints.add(y);
					
					if (!continuous)
					{
						endPoints.trimToSize();
						return endPoints;
					}
				}
				
				neighbourCount = 0;
			}
		}
		
		if (debugging)
		{
			System.out.println("The pattern " + patternName + " has " + endPointCount + (endPointCount > 1 ? " endpoints." : "endpoint."));
		}
		
		endPoints.trimToSize();
		
		return endPoints;
	}

	// Determines the image's aspect ratio
	public static float aspectRatio(int[][] pattern, boolean printResults)
	{
		int width = pattern[0].length;
		int height = pattern.length;
		
		int firstX = width, lastX = 0;
		int firstY = height, lastY = 0;

		// Find leftmost pixel
		for (int i = 0; i != height; ++i)
		{
			for (int j = 0; j != width; ++j)
			{
				if (pattern[i][j] != 0)
				{
					if (j < firstX)
					{
						firstX = j;
					}
					
					break;
				}
			}
		}
		
		// Find rightmost pixel
		for (int i = 0; i != height; ++i)
		{
			for (int j = width - 1; j != -1; --j)
			{
				if (pattern[i][j] != 0)
				{
					if (j > lastX)
					{
						lastX = j;
					}
					
					break;
				}
			}
		}
		
		// Find topmost pixel
		for (int i = 0; i != width; ++i)
		{
			for (int j = 0; j != height; ++j)
			{
				if (pattern[j][i] != 0)
				{
					if (j < firstY)
					{
						firstY = j;
					}
					
					break;
				}
			}
		}
		
		// Find bottommost pixel
		for (int i = 0; i != width; ++i)
		{
			for (int j = height - 1; j != -1; --j)
			{
				if (pattern[j][i] != 0)
				{
					if (j > lastY)
					{
						lastY = j;
					}
					
					break;
				}
			}
		}
		
		width = lastX - firstX;
		height = lastY - firstY;
		
		if (printResults) System.out.println("The aspect ratio is " + ((float)width / height));
		
		return ((float)width / height);
	}

	// Determines the average distance from center with standard deviation
	public static float[] averageDistanceFromCenter(int[][] pattern, boolean printResults)
	{
		int width = pattern[0].length;
		int height = pattern.length;
		
		float centerX = (float)(width + 1) / 2;
		float centerY = (float)(height + 1) / 2;
		float currentDistance = 0;
		
		if (printResults) System.out.println("Center is " + centerX + "," + centerY);
		
		float avgDistance = 0, stdDeviation = 0;
		float[] result = new float[2];
		
		ArrayList<Float> distances = new ArrayList<Float>();
		
		// Find the distance for each pixel
		for (int i = 0; i != height; ++i)
		{
			for (int j = 0; j != width; ++j)
			{
				if (pattern[i][j] == 0) continue;
				
				currentDistance = (float)(Math.sqrt(Math.pow((j - centerX), 2) + Math.pow((i - centerY), 2)));
				distances.add(currentDistance);
			}
		}
		
		distances.trimToSize();
		
		// Calculate average
		for (Float distance : distances)
		{
			avgDistance += distance;
		}
		
		if (printResults) System.out.println("Distance sum is " + avgDistance);
		
		avgDistance /= distances.size();
		
		if (printResults) System.out.println("Dividing by " + distances.size() + ", avg is " + avgDistance);
		
		result[0] = avgDistance;
		
		// Calculate the standard deviation
		for (Float distance : distances)
		{
			stdDeviation += Math.pow(distance - avgDistance, 2);
		}
		
		if (printResults) System.out.println("Deviation sum is " + stdDeviation);
		
		stdDeviation /= distances.size();
		
		if (printResults) System.out.println("Dividing by " + distances.size() + ", variance is " + stdDeviation);
		
		stdDeviation = (float)Math.sqrt(stdDeviation);
		
		if (printResults) System.out.println("Taking the square root, std dev is " + stdDeviation);
		
		result[1] = stdDeviation;
		
		if (printResults)
		{
			System.out.println("The average distance from center is " + avgDistance +
						       " with a standard deviation of " + stdDeviation + "\n");
		}
		
		return result;
	}
}